package com.g01.hj;

import com.g01.qt.Node;

import java.util.HashSet;

public class LinkNodeHaveRing {
    public static void main(String[] args) {
        // 先来一个没环
        int[] a = {1, 2, 3, 4, 5};
        Node al = Node.createLinkNode(a);
        Node f = FindRing.useSet(al);
        System.out.println(f == null ? "没环" : f.getData());
        f = FindRing.useDoubleF(al);
        System.out.println(f == null ? "没环" : f.getData());
        // 建一个环 5->3
        assert al != null;
        al.getNext().getNext().getNext().getNext().setNext(al.getNext().getNext());
        f = FindRing.useSet(al);
        System.out.println(f == null ? "没环" : f.getData());
        f = FindRing.useDoubleF(al);
        System.out.println(f == null ? "没环" : f.getData());
    }
}

class FindRing {
    // 用集合求解
    static Node useSet(Node head) {
        HashSet<Node> set = new HashSet<>();
        Node f = head;
        while (f != null) {
            if (set.contains(f)) {
                return f;
            } else {
                set.add(f);
                f = f.getNext();
            }
        }
        return null;  // 说明没有环
    }

    // 用双指针
    static Node useDoubleF(Node head) {
        Node slow = head;
        Node quick = head;
        do {
            slow = slow.getNext();
            try {
                quick = quick.getNext().getNext();  // 刚好在最后一个节点的时候第二个 getNext() 错误
            } catch (NullPointerException e) {
                quick = null;
            }
        } while (slow != quick && quick != null);
        if (quick == null) {
            return null;  // 没有环
        }
        while (head != slow) {  // 找环入口
            head = head.getNext();
            slow = slow.getNext();
        }
        return head;
    }
}
